# 作者： 李泉志
# 2025年01月13日11时37分秒
# 2947029073@qq.com

"""
4.2.2 排序算法
    针对排序算法，掌握通常的 8 种排序算法即可，依次是 冒泡，选择，插入，希尔，快
    排，堆排，归并，计排。
    对于排序算法分为以下 5 类：
        插入类：插入排序，希尔排序
        选择类：选择排序，堆排序
        交换类：冒泡排序，快速排序
        归并类：归并排序
        分配类：基数排序(计数排序，桶排序)，通过用额外的空间来”分配”和”收集”来实现排
        序，它们的时间复杂度可达到线性阶：O(n)
    实际面试面的最多的是快速排序，堆排序，还有计数排序
"""
import random
import time
import sys

sys.setrecursionlimit(1000000)  # 递归深度限制


class Sort:
    def __init__(self, n):
        """
        n: 待排序数组的长度
        :param n: int
        """
        self.len = n
        self.arr = [0] * n
        self.random_data()

    def random_data(self):
        for i in range(self.len):
            self.arr[i] = random.randint(0, 98)

    def partition(self, left, right):
        arr = self.arr
        # k左边的数都比pivot小，k及右边的数都比pivot大
        k = i = left
        random_pos = random.randint(left, right)  # 左闭右闭
        arr[left], arr[random_pos] = arr[random_pos], arr[left]  # 随机选择一个pivot
        for i in range(left, right):
            if arr[i] < arr[right]:
                arr[i], arr[k] = arr[k], arr[i]
                k += 1
        arr[k], arr[right] = arr[right], arr[k]
        return k

    def quick_sort(self, left, right):
        if left < right:
            pivot = self.partition(left, right)
            self.quick_sort(left, pivot - 1)
            self.quick_sort(pivot + 1, right)

    def adjust_max_heap(self, pos, len):
        """
        :param pos: 堆的根节点
        :param len: 堆的长度
        :return:
        """
        dad = pos
        son = 2 * pos + 1
        while son < len:
            if son + 1 < len and self.arr[son] < self.arr[son + 1]:
                son += 1
            if self.arr[dad] < self.arr[son]:
                self.arr[dad], self.arr[son] = self.arr[son], self.arr[dad]
                dad = son
                son = 2 * dad + 1
            else:
                break

    def heap_sort(self):
        for parent in range(self.len // 2 - 1, -1, -1):
            self.adjust_max_heap(parent, self.len)
        arr = self.arr
        for i in range(self.len - 1, 0, -1):
            arr[0], arr[i] = arr[i], arr[0]
            self.adjust_max_heap(0, i)

    def test_time(self, func, *args):
        start_time = time.time()
        func(*args)
        end_time = time.time()
        print("用时：", end_time - start_time)


if __name__ == '__main__':
    # s = Sort(10)
    # print(s.arr)
    # s.quick_sort(0, 9)
    # s.heap_sort()
    # print(s.arr)
    s2 = Sort(100000)
    # s2.test_time(s2.quick_sort, 0, 99999)
    s2.test_time(s2.heap_sort)

